Partition equal subset sum

Time: O(NxS); Space: O(S); medium

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Notes:

  • Each of the array element will not exceed 100.

  • The array size will not exceed 200.

Example 1:

Input: nums = [1, 5, 11, 5]

Output: True

Explanation:

  • The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1, 2, 3, 5]

Output: False

Explanation:

  • The array cannot be partitioned into equal sum subsets.

[3]:

class Solution1(object):
    """
    Time: O(N*S), S is the SUM of nums
    Space: O(S)
    """
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s % 2:
            return False

        dp = [False] * (s//2 + 1)
        dp[0] = True
        for num in nums:
            for i in reversed(range(1, len(dp))):
                if num <= i:
                    dp[i] = dp[i] or dp[i - num]

        return dp[-1]

[4]:

s = Solution1()

nums = [1, 5, 11, 5]
assert s.canPartition(nums) == True

nums = [1, 2, 3, 5]
assert s.canPartition(nums) == False